#include "decisionTree.h"
#include <vector>
#include <hash_map>

#include <boost/utility.hpp>

#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_io.hpp>
#include <boost/dynamic_bitset.hpp>

using namespace __gnu_cxx ;

enum DIR
{
    X_DIR = 0 ,
    Y_DIR
} ;

enum Orientation {
    R0 = 0 ,
    R90 ,
    R180 ,
    R270 ,
    FR0 ,
    FR90 ,
    FR180 ,
    FR270 ,
    MAXORIENT
} ;

const std::string OrientationStr[MAXORIENT] = { "R0", "R90", "R180", "R270", "FR0",
                                                "FR90", "FR180", "FR270" } ;

enum Pentominoe_Alphabet
{  
    ALPHA_L = 0 ,
    ALPHA_V ,
    ALPHA_Y ,
    ALPHA_T ,
    ALPHA_P ,
    ALPHA_U ,
    ALPHA_F ,
    ALPHA_N ,
    ALPHA_Z ,
    ALPHA_I ,
    ALPHA_W ,
    ALPHA_X ,
    MAX_ALPHA
} ;

const char PentominoeChars[MAX_ALPHA] = { 'L', 'V', 'Y', 'T', 'P', 'U', 'F', 'N', 'Z',
                                          'I', 'W', 'X' } ;

typedef boost::tuple<unsigned int, unsigned int> UIntPair ;
typedef boost::tuple<int, int> IntPair ;
typedef boost::tuple<char, Orientation, UIntPair>  SolnSetItem ;

const int COS90  = 0 ;
const int SIN90  = 1 ;
const int COS180 = -1 ;
const int SIN180 = 0 ;
const int COS270 = 0 ;
const int SIN270 = -1 ;

const int CosMinusTheta = 1 ;  // 1  * COS(Theta)
const int SinMinusTheta = -1 ; // -1 * SIN(Theta)

// Forward Declaration of classes.
class OutOfBoundException ;
class BindException ;
class UnbindException ;
class InvalidOrientationException ;
class InvalidLetterException ;
class MatrixModel ;
class PentominoesModel  ;
class PentominoesPiece  ;
class PentominoesState  ;
class MapConstraint ;
class GoalConstraint  ;
class PentominoesTree ;

namespace __gnu_cxx
{
    template<> struct hash< PentominoesPiece* >
    {
        size_t operator()( const PentominoesPiece* x ) const
        {
  	    return ((size_t)(x)) ;
        }
    };
}


// This exception should be thrown, when a MatrixModel is being tried to be
// pasted on an existent model, but post the result of paste, the original model's
// dimension id getting changed.
class OutOfBoundException
{
    public :
        OutOfBoundException(UIntPair& data) : m_data(data) {}
        ~OutOfBoundException() {}

        virtual const char* what() const throw() ;
    private :
        UIntPair       m_data ; // first  : amount by which x is getting out of bound
                                // second : amount by which y is getting out of bound
} ;

// This exception should be thrown, when a MatrixModel(secondary) is being tried to be
// pasted on an existent model(primary), but any region where the pasting op is about
// to be done already contains 1 in the primnary model.
class BindException
{
    public :
        BindException(UIntPair& data) : m_data(data) {}
        ~BindException() {}

        virtual const char* what() const throw() ; 
    private :
        UIntPair       m_data ; // First (x,y) where the difference has occured.
} ;

// This exception should be thrown, when a MatrixModel(secondary) is being tried to be
// extracted from an existent model(primary), but any region where the extraction op is
// about to be done doesn't contain 1 or 0 in the primnary model at exact same location where
// secondary model contains 1 or 0.
class UnbindException
{
    public :
        UnbindException(UIntPair& data) : m_data(data) {}
        ~UnbindException() {}

        virtual const char* what() const throw() ; 
    private :
        UIntPair       m_data ; // First (x,y) where the difference has occured.
} ;

class InvalidOrientationException
{
    public :
        InvalidOrientationException(Orientation orient) : m_orient(orient) {}
        ~InvalidOrientationException() {}

        virtual const char* what() const throw() ; 
   private :
        Orientation         m_orient ;
} ;

class InvalidLetterException
{
    public :
        InvalidLetterException(Pentominoe_Alphabet letter) : m_letter(letter) {}
        ~InvalidLetterException() {}

        virtual const char* what() const throw() ; 
   private :
        Pentominoe_Alphabet         m_letter ;
} ;

// Implement the accessors properly which will allow the user not to really copy the
// matrix from one form to other... without altering the model.
// Note :
//      The matrix model is not used to really use matrix operations like addn/sub/mult
// but to get/set the elements of the boolean matrix. Also the two primary operations
// MatrixModel provides is bind/unbind a subMatrix on the existing matrix. The Bind/Unbind
// operation will only happen if the current MatrixModel has empty/filled position already
class MatrixModel
{
    public :
        MatrixModel() ;
        MatrixModel(UIntPair& matDimension) ;
        MatrixModel(unsigned int rowCnt, unsigned int colCnt) ;
        ~MatrixModel() ;

        // Always does deep compare....
        // bool                operator==(const MatrixModel& matrix) const { return deepCompare(matrix) ; }
        bool                operator==(const MatrixModel& matrix) const { return modelCompare(matrix) ; }

        MatrixModel&        operator=(const MatrixModel& model) ;
        //Have other boolean operators, != operator and other important operator overloaded.
        
        bool                modelCompare(const MatrixModel& matrix) const ;
        bool                deepCompare(const MatrixModel& matrix) const ;

        unsigned int        numRows() const ;
        unsigned int        numCols() const ; 
        // Returns the dimension as it got it.
        UIntPair            getDimension() const { return m_dimension ; }

        Orientation         getOrientation() const { return m_orient ; }
        void                setOrientation(Orientation orient) { m_orient = orient ; }

        // Algo :
        //      1. applyInverseTransform and get new set of worlCoord on the world coord at step 1 
        //      2. get the value at the index got at step1
        // Note :
        //      The following two functions are fine when we need to just make change at one posn of the
        //      matrix. It would be very costly if we are working on matrix operations like add, sub, mult etc
        bool                getValAt(unsigned int row, unsigned int col, bool postTransform=true) const ; //(row, col) is worldPos
        void                setValAt(unsigned int row, unsigned int col, bool val, bool postTransform=true) ; // (row, col) is worldPos

        // Lowest pos will be returned as would be in transformed matrix
        bool                getLowestPosWithVal(bool val, UIntPair& worldPos, DIR dir) const ;

        void                bindMatrixAt(const MatrixModel& matrix, const UIntPair& worldPos) ;
        void                unbindMatrixFrom(const MatrixModel& matrix, const UIntPair& worldPos) ;
        // When reverse is true, the question which is asked is whether the extraction(unbinding) of the given model
        // from the current model is possible or not.
        bool                isBindingPossibleAt(const MatrixModel& matrix,
                                                const UIntPair& pos, bool reverse=false) const ;
        bool                isAnyBitSet() const ;
        void                clearModel() ;

        bool                findDiffLoc(UIntPair& loc, bool curModelVal, bool goalModelVal,
                                        const MatrixModel& goalModel, DIR dir) const ;
        bool                shiftNeededToGetValAtTopLeft(bool val, DIR dir,
                                                         unsigned int& shift) const ;
        void                initialize(unsigned int row, unsigned int col) ;   
        void                printModelWithChar(char ch) const ;

        static IntPair      getMatrixCoord(const IntPair& worldCoord, const int transformMat[][3]) ;
        
    private :
        std::vector< boost::dynamic_bitset<> > m_data ;
        UIntPair            m_dimension ;
        Orientation         m_orient ;


        // For different orientation we need to apply different transformation matrix
        // Note : Dont do matrix multiplication every time as its going to be constant
        //        break it down to a simple expression. Returns worlCord after inverse
        //        transformation.
        UIntPair            applyInverseTransformToWorld(const UIntPair& worldCoord) const ;

        static IntPair      matrixMult(const int mat1[3][3], const IntPair& coord) ;
        static void         matrixMult(const int mat1[3][3], const int mat2[3][3],
                                       int resMat[3][3]) ;

        void                getInverseTransformMat(int mat[3][3]) const ;

        void                getR0InverseTransformMat(int mat[3][3]) const ;
        void                getR90InverseTransformMat(int mat[3][3]) const ;
        void                getR180InverseTransformMat(int mat[3][3]) const ;
        void                getR270InverseTransformMat(int mat[3][3]) const ;
        void                getFR0InverseTransformMat(int mat[3][3]) const ;
        void                getFR90InverseTransformMat(int mat[3][3]) const ;
        void                getFR180InverseTransformMat(int mat[3][3]) const ;
        void                getFR270InverseTransformMat(int mat[3][3]) const ;

        // Only do transformed val compare for current matrix.
        bool                doCurTransformedValCompare(const MatrixModel& matrix) const ;

        // Do transformed val compare for both current matrix and the matrix passed as argument
        bool                doTransformedValCompare(const MatrixModel& matrix) const ;

        void                initTranslateMat(int transMat[3][3]) const ;
        void                initRotateMat(int rotMat[3][3]) const ;
        void                initFlipMat(int flipMat[3][3]) const ;
} ;

class PentominoesModel : public Model
{
      public :
          PentominoesModel(UIntPair& dimension, bool goalModel=false) ;
          ~PentominoesModel() ;

          // Equality should consider equality of all possible orientation of the model
          bool              operator==(const Model& model) const ;

          bool              lowestEmptyPos(UIntPair& pos, DIR dir) const ;
          bool              isMappingPossible(const UIntPair& mapLoc, const PentominoesPiece& pent) const ;
          bool              isUnmappingPossible(const UIntPair& mapLoc, const PentominoesPiece& pent) const ;
          bool              mapPieceToModel(const UIntPair& mapLoc, PentominoesPiece& pent) ;
          bool              unmapPieceFromModel(const UIntPair& mapLoc, PentominoesPiece& pent) ;

          // If the MatrixModel contains even a single bit set and the size of the hash_map is empty
          // the goal Model will be true.
          bool              isGoalModel() const ;
          void              setModelAsGoalModel(bool val) { m_goalModel = val ; }

          bool              hasGoalReached(const PentominoesModel& goalModel) const { return *this == goalModel ; }
          void              extractPentominoesState(std::vector<SolnSetItem>& solnSet) const ;

          UIntPair          getDimension() const { return p_data.getDimension() ; }
          Model*            getNewModelWithSelfTraits() const ;

          void              printModel() const { p_data.printModelWithChar('1') ; }

          const MatrixModel getMatrixModel() const { return p_data ; }

          void              setGoalMatrixModel(MatrixModel& matData) { p_data = matData ;
                                                                       m_goalModel = true ;}
      private :
          MatrixModel                             p_data ;
	  hash_map< PentominoesPiece*, 
                    UIntPair, 
                    hash<PentominoesPiece*> >     m_pieces ; // Goal will not contain any pieces.
	  bool                                    m_goalModel ;
} ;

class PentominoesPiece : public Item
{
    public :
        //  L, V, Y, T, P, U, F, N, Z, I, W, X

        PentominoesPiece(Pentominoe_Alphabet alphabet) ;
        ~PentominoesPiece() ;

        // Functions...
        bool                perturb() ;
        const MatrixModel&  getMatrixModel() const { return m_bitmapModel ; }

        char                getAlphabet() const ;
	std::string         getOrientationStr() const ;

        Orientation         getOrientation() const { return m_bitmapModel.getOrientation() ; }
        void                setOrientation(Orientation orient) { m_bitmapModel.setOrientation(orient) ; }

        std::string         getPieceInfo() const ;
    private :
        // 12 Piceces of Pentominoes are :
        //  L, V, Y, T, P, U, F, N, Z, I, W, X
        Pentominoe_Alphabet m_letter ;
        MatrixModel         m_bitmapModel ;  // Model keeps the orientation as well

        void                initializeMatrixModel() ;
} ;

class PentominoesState : public State
{
    public :
        // Item will be stored by the base class.
        PentominoesState() : State() {}
        PentominoesState(const UIntPair& loc, PentominoesPiece* p_item, DIR dir) ;
        ~PentominoesState() ;

        void                initiateStateForSolution() ;
        bool                fixStateForSolution() ;
        void                resetStateOriginal() { m_shiftVal = 0 ; m_pieceLoc = m_originalLoc ; }
        bool                applyStateOnModel(Model* p_model) const ;
        bool                backtrackState(Model* p_model) const ;

        void                printState() const ;
        UIntPair            getPieceLoc() const { return m_pieceLoc ; }
    private :
        UIntPair            m_pieceLoc ; // This is also the loc which should be made true
        DIR                 m_dir ;
        unsigned int        m_shiftVal ;
        UIntPair            m_originalLoc ;

        bool                shiftStateToGetTrueAtLL() ;
} ;

class MapConstraint : public Constraint
{
    public :
        MapConstraint(std::string& name) : Constraint(name, PRE_CONSTRAINT, true) {}
	~MapConstraint() {}

        bool                isSatisfied(const Model* p_model, const Model* p_goalModel,
					const State* p_toState) const ;
    private :   
} ;

class GoalConstraint : public Constraint
{
    public :
        GoalConstraint(std::string& name) : Constraint(name, POST_CONSTRAINT, true) {}
	~GoalConstraint() {}

        bool                isSatisfied(const Model* p_model, const Model* p_goalModel,
					const State* p_toState) const ;
    private :
} ;

class PentominoesTree : public DecisionTree
{
    public :
        PentominoesTree() ;
        ~PentominoesTree() {}

        size_t              generateAllChildStates(const Solution& curState,
                                                   State* p_state) const ;
        size_t              generateNextChildState(const State* p_prevSiblingState,
						   const Solution& states,
						   State* p_parentState) const ;
        void                printSolution(const Solution& states) const ;

	std::string         getCurSolutionStateStr(const Solution& states) const ;

    private :
        bool                initializeModel() ;
        bool                buildStateZero() ;
        void                buildConstraints() ;
        void                initializeItems() ;
} ;


